\input{common/slides_common}

\newif\ifbook
\input{../shared/chisel}

\title{Refactor of State Machines}
\author{Martin Schoeberl}
\date{\today}
\institute{Technical University of Denmark\\
Embedded Systems Engineering}

\begin{document}

\begin{frame}
\titlepage
\end{frame}

\begin{frame}[fragile]{Outline}
\begin{itemize}
\item Repeat functions and parameters
\item Repeat finite-state machine with datapath
\item Factoring of finite-state machines
\item Input processing
\item Reset input
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Midterm Evaluation}
\begin{itemize}
\item Do we need this?
\item An anonymous Google form (no login required)
\item 15 minutes time during the break
\item We will look into it after the break
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Functions}
\begin{itemize}
\item Circuits can be encapsulated in functions
\item Each \emph{function call} generates hardware
\item A function is defined with \code{def} \emph{name}
\item Similar to methods in Java
\item Simple functions can be a single line
\end{itemize}
\begin{chisel}
  def adder(v1: UInt, v2: UInt) = v1 + v2
  
  val add1 = adder(a, b)
  val add2 = adder(c, d)
\end{chisel}
\end{frame}

\begin{frame}[fragile]{More Function Examples}
\begin{itemize}
\item Functions can also contain registers
\end{itemize}
\begin{chisel}
  def addSub(add: Bool, a: UInt, b: UInt) =
    Mux(add, a + b, a - b)

  val res = addSub(cond, a, b)

  def rising(d: Bool) = d && !RegNext(d)

  val edge = rising(cond)
\end{chisel}
\end{frame}

\begin{frame}[fragile]{The Counter as a Function}
\begin{itemize}
\item Longer functions in curly brackets
\item Last value is the return value
\end{itemize}
\begin{chisel}
def counter(n: UInt) = {
  
  val cntReg = RegInit(0.U(8.W))
  
  cntReg := cntReg + 1.U
  when(cntReg === n) {
    cntReg := 0.U
  }
  cntReg
}

val counter100 = counter(100.U)
\end{chisel}
\end{frame}

\begin{frame}[fragile]{Functional Abstraction}
\begin{itemize}
\item Functions for repeated pieces of logic
\item May contain state
\item Functions may return \emph{hardware}
\item More lightweight than a \code{Module}
\end{itemize}
\end{frame}

%\begin{frame}[fragile]{Functions}
%\begin{itemize}
%\item Example from Patmos execute stage
%\end{itemize}
%\begin{chisel}
%def alu(func: Bits, op1: UInt, op2: UInt): Bits = {
%  val result = UInt(width = DATA_WIDTH)
%  // some more lines...
%  switch(func) {
%    is(FUNC_ADD) { result := sum }
%    is(FUNC_SUB) { result := op1 - op2 }
%    is(FUNC_XOR) { result := (op1 ^ op2).toUInt }
%    // some more lines
%  }
%  result
%}
%\end{chisel}
%\end{frame}

\begin{frame}[fragile]{Parameterization}
\begin{chisel}
class ParamChannel(n: Int) extends Bundle {
  val data = Input(UInt(n.W))
  val ready = Output(Bool())
  val valid = Input(Bool())
}

val ch32 = new ParamChannel(32)
\end{chisel}
\begin{itemize}
\item Bundles and modules can be parametrized
\item Pass a parameter in the constructor
\end{itemize}

\end{frame}
\begin{frame}[fragile]{A Module with a Parameter}
\shortlist{../code/param_adder.txt}
\begin{itemize}
\item Parameter can also be a Chisel type
%\item Can also be a generic type:
%\item \code{class Mod[T <: Bits](param: T) extends...}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Use the Parameter}
\shortlist{../code/use_param_adder.txt}
\begin{itemize}
\item Can be used for the display multiplexing configuration
\item Different maximum value for the counter for the simulation and for the FPGA
\end{itemize}
\end{frame}



%\begin{frame}[fragile]{Show Example on ``Whiteboard''}
%\end{frame}

\begin{frame}[fragile]{FSM with Datapath}
\begin{itemize}
\item A type of computing machine
\item Consists of a finite-state machine (FSM) and a datapath
\item The FSM is the master (the controller) of the datapath
\item The datapath has computing elements
\begin{itemize}
\item E.g., adder, incrementer, constants, multiplexers, ...
\end{itemize}
\item The datapath has storage elements (registers)
\begin{itemize}
\item E.g., sum of money payed, count of something, ...
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{FSM-Datapath Interaction}
\begin{itemize}
\item The FSM controls the datapath
\begin{itemize}
\item For example, add 2 to the sum
\end{itemize}
\item By controlling multiplexers
\begin{itemize}
\item For example, select how much to add
\item Not adding means selecting 0 to add
\end{itemize}
\item Which value goes where
\item The FSM logic also depends on datapath output
\begin{itemize}
\item Is there enough money payed to release a can of soda?
\end{itemize}
\item FSM and datapath interact
\end{itemize}
\end{frame}


\begin{frame}[fragile]{Popcount Example}
\begin{itemize}
\item An FSMD that computes the popcount
\item Also called the Hamming weight
\item Compute the number of `1's in a word
\item Input is the data word
\item Output is the count
\item Code available at \href{https://github.com/schoeberl/chisel-book/blob/master/src/main/scala/PopCount.scala}{PopCount.scala}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Popcount Block Diagram}

\begin{figure}
  \includegraphics[scale=\scale]{../figures/popcnt-fsmd}
\end{figure}
\end{frame}


\begin{frame}[fragile]{Popcount Connection}
\begin{columns}
\column{0.6\textwidth}
\begin{itemize}
\item Input \code{din} and output \code{popCount}
\item Both connected to the datapath
\item We need some handshaking
\item For data input and for count output
\end{itemize}
\column{0.4\textwidth}
\begin{figure}
  \includegraphics[scale=0.45]{../figures/popcnt-fsmd}
\end{figure}
\end{columns}
\end{frame}

\begin{frame}[fragile]{Popcount Handshake}
\begin{columns}
\column{0.6\textwidth}
\begin{itemize}
\item We use a ready-valid handshake
\item When data is available valid is asserted
\item When the receiver can accept data ready is asserted
\item Transfer takes place when both are asserted
\end{itemize}
\column{0.4\textwidth}
\begin{figure}
  \includegraphics[scale=0.45]{../figures/popcnt-fsmd}
\end{figure}
\end{columns}
\end{frame}


\begin{frame}[fragile]{The FSM}
\begin{figure}
  \includegraphics[scale=\scale]{../figures/popcnt-states}
\end{figure}
\begin{itemize}
\item A Very Simple FSM
\item Two transitions depend on input/output handshake
\item One transition on the datapath output
\end{itemize}
\end{frame}

\begin{frame}[fragile]{The Datapath}
\begin{figure}
  \includegraphics[scale=0.65]{../figures/popcnt-data}
\end{figure}
\end{frame}

\begin{frame}[fragile]{Let's Explore the Code}
\begin{itemize}
\item In \href{https://github.com/schoeberl/chisel-book/blob/master/src/main/scala/PopCount.scala}{PopCount.scala}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Usage of an FSMD}
\begin{itemize}
\item Maybe the main part your vending machine is an FSMD?
\end{itemize}
\end{frame}



\begin{frame}[fragile]{Factoring FSMs}
\begin{itemize}
\item Divide a big problem into several smaller problems
\item Splitting a FSM into two or more
\begin{itemize}
\item Simplify the design
\end{itemize}
\item FSMs communicate via logic signals
\begin{itemize}
\item FSM provides input controls signals to another
\item FSM senses output from another
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Specification Of a Light Flasher}
\begin{itemize}
\item Inputs: \code{start}
\item Outputs: \code{light}
\item Operation:
\begin{itemize}
\item When in = 1, FSM goes through 5 sequences:
\begin{itemize}
\item On-Off-On-Off-On
\end{itemize}
\item Each On sequence (\code{flash}):
\begin{itemize}
\item out = 1
\item 6 cycles long
\end{itemize}
\item Each Off sequence (\code{space}):
\begin{itemize}
\item out = 0
\item 4 cycles long
\end{itemize}
\item After 5 sequences, FSM goes back to \code{off} state to wait for new input
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Light Flasher State Diagram}
\begin{itemize}
\item Example from Dally, Chapter 17
\item Copyright figure, so show it from older slides
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Specification Change}
\begin{itemize}
\item We have a flat FSM with 27 states
\begin{itemize}
\item 27 \code{is(state)} statements
\end{itemize}
\item If we change the specification to
\begin{itemize}
\item 12 cycles for each flash
\item 4 flashes
\item 7 cycles between flashes
\item Complete change of \code{switch} statement
\item Now 70 \code{is} statements!
\end{itemize}
\item This does not scale
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Factor Light Flasher}
\begin{itemize}
\item Factor out counting on and off intervals
\begin{itemize}
\item Into a timer
\item Reduces 6 and 4 states sequences into two single states
\end{itemize}
\item Results in
\begin{itemize}
\item a master FSM and
\item a timer FSM
\end{itemize}
\item Simplifies FSMs
\item Allows easier change of interval lengths
\end{itemize}
\end{frame}


%\begin{frame}[fragile]{Working Break}
%\begin{itemize}
%\item Build your own ``camera'' stand
%\item 20 minutes
%\item Show your solution to the others at the end of the break
%\begin{itemize}
%\item Don't expose it too early ;-)
%\end{itemize}
%\end{itemize}
%\end{frame}

\begin{frame}[fragile]{Factored Light Flasher}
\begin{figure}
  \includegraphics[scale=\scale]{../figures/flasher}
\end{figure}
\begin{itemize}
\item Time loads value 5 or 3, based in \code{timerSelect}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Timer Specification}
\begin{itemize}
\item Two inputs
\begin{itemize}
\item \code{timerLoad} to load the down counter
\item \code{timerSelect} to select between 6 and 4 cycles counting
\end{itemize}
\item Output
\begin{itemize}
\item \code{timerDone} is 1 when counter has completed the countdown
\item Remains asserted until counter reloaded
\end{itemize}
\item Counter can be (re)loaded in any state
\begin{itemize}
\item When not loaded it counts down to zero
\end{itemize}
\item Similar to the timer we looked at two weeks ago
\end{itemize}
\end{frame}

\begin{frame}[fragile]{The Timer FSM}
\shortlist{../code/flasher_timer.txt}
\end{frame}

\begin{frame}[fragile]{The Master FSM}
\begin{itemize}
\item Show in IntelliJ
\item Run test and show waveform
\end{itemize}
\end{frame}


%\begin{frame}[fragile]{State Diagram of Factored Light Flasher}
%\begin{itemize}
%\item yyy
%\end{itemize}
%\end{frame}
%
%\begin{frame}[fragile]{Waveforms from simulation of light-flasher FSM}
%\begin{itemize}
%\item yyy
%\end{itemize}
%\end{frame}

\begin{frame}[fragile]{Result of Refactoring}
\begin{itemize}
\item State of original flat FSM has been separated
\item The part of cycle counting in the counter
\item Part flash or space in master FSM
\item Represent original 27 states in just two 6 states FSMs
\item 
\item BTW: the master FSM is a Mealy FSM
\end{itemize}
\end{frame}

\begin{frame}[fragile]{20' Break}
\begin{itemize}
\item Mid-term evaluation
\item Will send the link per email and Slack (now)
\item We talk about the results after the break
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Still Redundancy in FSM}
\begin{itemize}
\item \code{flash1}, \code{flash2}, and \code{flash3} same function
\item \code{space1} and \code{space2} same function
\item Refactor number of remaining flashes
\item Master FSM states: \code{off}, \code{flash},
and \code{space}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Factor out ``flash number''}
\begin{figure}
  \includegraphics[scale=\scale]{../figures/flasher2}
\end{figure}
\end{frame}

\begin{frame}[fragile]{Counter}
\shortlist{../code/flasher2_counter.txt}
\begin{itemize}
\item Loaded with 2 for 3 flashes
\item Counts the \emph{remaining} flashes
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Code of Flasher2}
\begin{itemize}
\item Show in IntelliJ
\item Run test and show waveform
\end{itemize}
\end{frame}



%\begin{frame}[fragile]{State diagram of twice-factored light flasher}
%\begin{itemize}
%\item yyy
%\end{itemize}
%\end{frame}

\begin{frame}[fragile]{Benefits of Refactored Solution}
\begin{itemize}
\item Master FSM has just three states: \code{off}, \code{flash}, and \code{space}
\item Change of intervals or number of flashes needs no change in the FSM
\item Smaller components are easier to read and simpler to test individually
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Usage in your VM}
\begin{itemize}
\item Maybe factor out the edge detection for the button(s)
\item Use a timer for more advanced user interface
\begin{itemize}
\item Blinking LED on some error
\item Write text as a banner in the 7-segment display
\item ...
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Input Processing}
\begin{itemize}
\item Input signals are not synchronous to the clock
\item May violate setup and hold time of a flip-flop
\item Can lead to metastability
\item Signals need to be \emph{synchronized}
\item Using two flip-flops
\item Metastability cannot be avoided
\item Assumption is:
\begin{itemize}
\item First flip-flop may become metastable
\item But will resolve within the clock period
\end{itemize}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Input Synchronizer}
\begin{figure}
  \includegraphics[scale=\scale]{../figures/synchronizer}
\end{figure}
\shortlist{../code/input_sync.txt}
\end{frame}

\begin{frame}[fragile]{Bouncing Buttons}
\begin{itemize}
\item Buttons and switches need some time to transition between on and off
\item May bounce between the two values
\item Without processing we detect more than one event
\item Solution is to filter out bouncing
\begin{itemize}
\item Can be done electrically (R + C + Schmitt trigger)
\item That is why you have the extra PCB with the buttons
\item But we can also do this digitally
\end{itemize}
\item Assume  bouncing time $t_{bounce}$
\item Sample at a period $T > t_{bounce}$
\item Only use sampled signal
\end{itemize}
\end{frame}


\begin{frame}[fragile]{Sampling for Debouncing}
\begin{figure}
  \includegraphics[scale=\scale]{../figures/debounce}
\end{figure}
\end{frame}


\begin{frame}[fragile]{Sampling for Debouncing}
\shortlist{../code/input_fac.txt}
\shortlist{../code/input_debounce.txt}
\begin{itemize}
\item We already know how to do this!
\item Just generate timing with a counter
\item We sample at 100 Hz (bouncing below 10 ms)
\end{itemize}
\end{frame}


\begin{frame}[fragile]{Noisy Input Signal}
\begin{itemize}
\item Sometimes input may be noisy
\item May contain spikes
\item Filtering with majority voting
\item Majority voting of the sampled input signal
\item However, this is seldom needed
\item Not for the buttons you have
\end{itemize}
\end{frame}


\begin{frame}[fragile]{Majority Voting}
\begin{figure}
  \includegraphics[scale=\scale]{../figures/majority}
\end{figure}
\end{frame}


\begin{frame}[fragile]{Majority Voting}
\shortlist{../code/input_majority.txt}
\end{frame}

\begin{frame}[fragile]{Detecting the Press Event}
\begin{itemize}
\item Edge detection
\item You have seen this before
\item Just to complete the input procssing
\end{itemize}
\shortlist{../code/input_usage.txt}
\end{frame}

\begin{frame}[fragile]{Combine Input Processing with Functions}
\begin{itemize}
\item Using small functions to abstract the processing
\item \href{https://github.com/schoeberl/chisel-book/blob/master/src/main/scala/Debounce.scala}{Debounce.scala}
\end{itemize}
\end{frame}

\begin{frame}[fragile]{Reset is an Asynchronous Signal}
\begin{itemize}
\item Needs a input synchronizer
\item Usually hidden in Chisel, but easy to access
\item Do the reset synchronizer at the top level module
\end{itemize}
\shortlist{../code/sync_reset.txt}
\end{frame}

\begin{frame}[fragile]{Today's Lab}
\begin{itemize}
\item Driving your 7-segment decoder
\item Use a counter to count from 0 to 15, driving your display
\item Use another counter to generate your timing
\begin{itemize}
\item We talked about this today
\end{itemize}
\item You clock on the board is 100 MHz
\item The given tester does only generate a waveform, no testing
\item Use a different maximum count value for waveform debugging
\item Then synthesize it for the FPGA
\item Show a TA your working design
\item \href{https://github.com/schoeberl/chisel-lab/tree/master/lab8}{Lab 8}
\end{itemize}
\end{frame}



\begin{frame}[fragile]{Summary}
\begin{itemize}
\item Divide a bigger problem into smaller ones
\begin{itemize}
\item Easier to design
\item Easier to test
\item Sometimes only feasible solution
\end{itemize}
\item Factoring state machines
\begin{itemize}
\item Separate state into multiple `orthogonal' state variables
\item Each is simpler to handle (fewer states)
\item ``Factors out'' repetitive sequences
\item Hierarchical structure
\end{itemize}
\end{itemize}
\end{frame}




\end{document}

%\begin{frame}[fragile]{xxx}
%\begin{itemize}
%\item yyy
%\end{itemize}
%\end{frame}
